package sort;

import java.util.Arrays;

public class MergeSort {
	public static void main(String[] args) {
		int[] arr = {2,33,4,56,7,88,21};
		sort(arr,0,arr.length-1);
		System.out.println(Arrays.toString(arr));
	}

	private static void sort(int[] arr, int start, int end){
		if(start >=end){
			return;
		}
		int mid = (start + end) >> 1;
		//1.拆开
		sort(arr,start,mid);
		sort(arr,mid+1,end);
		//2.分而治之，合并
		mergeSort(arr,start,mid,end);
	}

	private static void mergeSort(int[] arr, int start, int mid, int end) {
		//创建临时数组
		int[] tempArr = new int[end+1];

		//将两数组进行比较
			//设定两个指针  左边数组，右边数组
			int left = start;
			int right = mid +1;
			//在设定一个指针，用于当前需要存储临时数组的位置
			int temPoint = start;
		while(left<=mid && right <= end){
			//将比较的结果放到新数组中
			//需求：升序
			tempArr[temPoint++] = arr[left] > arr[right] ? arr[right++]:arr[left++];
		}
		//处理过长的数组部分的数据
		if(left<=mid){
			for (int i = left; i <=mid ; i++) {
				tempArr[temPoint] = arr[left];
			}
		}
		if(right<=end){
			for (int i = right; i <=end ; i++) {
				tempArr[temPoint] = arr[right];
			}
		}
		//将临时表覆盖原数组的位置
		System.arraycopy(tempArr,start,arr,start,end-start+1);
	}
}
